 #define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        //1.准备
        unordered_map<int, vector<int>> edges;
        vector<int> in(numCourses);

        //2.建图
        for (auto& e : prerequisites)
        {
            int a = e[0], b = e[1];
            edges[b].push_back(a);
            in[a]++;
        }

        //3.进行拓扑排序
        queue<int> q;

        //a.把所有入度为0的点加入到队列中
        for (int i = 0; i < numCourses; i++)
            if (in[i] == 0)
                q.push(i);

        //b.bfs
        while (q.size())
        {
            int t = q.front();
            q.pop();

            for (int a : edges[t])
            {
                in[a]--;
                //将所有入度变为为0的点加入到队列中
                if (in[a] == 0) q.push(a);
            }
        }

        //4.判断是否有环
        for (int i = 0; i < numCourses; i++)
            if (in[i]) return false;

        return true;
    }
};

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        //1.准备
        unordered_map<int, vector<int>> edges;
        vector<int> in(numCourses);//记录该元素的入度

        //2.建图
        for (auto& e : prerequisites)
        {
            int a = e[0], b = e[1];
            edges[b].push_back(a);
            in[a]++;
        }
        //拓扑排序
        queue<int> q;
        //将所有入度为0的数添加进队列
        for (int i = 0; i < numCourses; i++)
            if (in[i] == 0)
                q.push(i);


        //3.bfs
        vector<int> ret;
        while (q.size())
        {
            int t = q.front();
            ret.push_back(t);
            q.pop();
            for (auto& a : edges[t])
            {
                in[a]--;
                if (in[a] == 0) q.push(a);
            }
        }

        //4.判断是否有环
        if (ret.size() == numCourses) return ret;
        else return vector<int>();
    }
};

class Solution {
public:
    unordered_map<char, unordered_set<char>> edges;
    unordered_map<char, int> in;
    bool check;

    string alienOrder(vector<string>& words) {
        //建图 + 初始化列表
        for (auto& e : words)
        {
            for (auto ch : e)
            {
                in[ch] = 0;
            }
        }

        int n = words.size();
        for (int i = 0; i < n; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                add(words[i], words[j]);
                if (check) return "";
            }
        }

        //拓扑排序
        queue<char> q;
        //将入度为零的数添加的队列中去
        for (auto& [a, b] : in)
        {
            if (b == 0) q.push(a);
        }

        string ret;
        while (q.size())
        {
            char t = q.front(); q.pop();
            ret += t;
            for (char ch : edges[t])
            {
                if (--in[ch] == 0) q.push(ch);
            }
        }

        //判断是否有环
        for (auto& [a, b] : in)
            if (b != 0) return "";

        return ret;
    }

    void add(string& s1, string& s2)
    {
        int n = min(s1.size(), s2.size());
        int i = 0;
        for (; i < n; i++)
        {
            if (s1[i] != s2[i])
            {
                char a = s1[i], b = s2[i];
                if (!edges.count(a) || !edges[a].count(b))
                {
                    edges[a].insert(b);
                    in[b]++;
                }
                break;
            }
        }
        if (i == s2.size() && i < s1.size()) check = true;

    }
};